#!/usr/bin/env ruby

#Philip C. Pilosi   and     Todd R. Silvia 
#   668828058                  660667901

# File: DFSSearch.rb
# Usage: This file is passed a 20x20 board and searches for the goals
# 		 via depth first search.




#Global Variables
SIZE_OF_ROW = 22;
DIRECTIONS = [-1,-22,1,22]; #Left,Up,Right,Down
$nodesToVisit = [];
$nodesVisited = [];
$solutionCounter = 0;

#Prints a correct looking board
def printBoard(board)
	for i in 0..483
		print board[i]+ " ";
		if(((i+1) % 22) == 0)
			puts
		end
	end
end


#Check to see if given location is blank
def checkBlank(board,index)
	if(board[index] == ".")
		true;
	else
		false;
	end

end

#Check if space is a goal location.
def checkGoal(board,index)
	if(board[index] == "G")
		true;
	else
		false;
	end
end

#Determine the direction of the current move and set relative symbol
def determineSymbol(direction)
	symbol = "s";
	if(direction == 1)
		symbol = ">";
	end
	
	if(direction == 22)
		symbol = "v";
	end
	
	if(direction == -1)
		symbol = "<";
	end
	
	if(direction == -22)
		symbol = "^";
	end
	symbol;
end

#Print the current path to the found goal location.
def printPath(board)
	displayBoard = Marshal.load(Marshal.dump(board));
	upperBound = $nodesToVisit.length-2; #Find out how many moves were made.
	
	for i in 1..upperBound
		currentIndex = $nodesToVisit[i];#Test: Grab current move and store in variable.
		lastIndex = $nodesToVisit[i-1]; #Grab the last node
		displayBoard[Integer(currentIndex)] = determineSymbol(Integer(currentIndex) - Integer(lastIndex)); #Still being tested.
	end
	
	printBoard(displayBoard); #Print the game board.
end


##Recursive version of DFS search on Maze.
##The search is applied to the maze as a whole and when
##a solution is found at that current moment the path 
##taken there is printed as a
def applyDfs(dfsBoard,originalBoard)
	path = [];
	if($nodesToVisit.length > 0)
		#Stack is not empty, done searching maze.
		currentNode = $nodesToVisit[($nodesToVisit.length - 1)];
	end
	
	goalFound = checkGoal(dfsBoard,currentNode); #Check if the current node is a goal spot.
	if(goalFound == true)
		puts "Goal Found :" + currentNode.to_s;
		printPath(originalBoard);
		puts "Solution sequence, in order of index locations";
		#print $nodesToVisit;
		puts;
		$solutionCounter = $solutionCounter + 1;
		dfsBoard[currentNode] = "v";
	end
	
	for i in 0..3
		direction = DIRECTIONS[i]; #Grab a direction from array of directions
		nodeToProcess = Integer(currentNode) + Integer(direction); #Determine location of node to process
		alreadyVisited = checkBlank(dfsBoard,nodeToProcess); #Check to see if this node is already marked as visited.
		if(alreadyVisited == true)
			dfsBoard[nodeToProcess] = "v"; #Mark node as visited
			$nodesToVisit.push(nodeToProcess); #Add new node to the stack of visited nodes.
			applyDfs(dfsBoard,originalBoard); #Apply algorithm to the newly visited node.
		
		else
			goalFound = checkGoal(dfsBoard,nodeToProcess);
			if(goalFound == true)
				$nodesToVisit.push(nodeToProcess);
				applyDfs(dfsBoard,originalBoard);
			end
		end
		
	end
	$nodesToVisit.pop;
end

##################################
######## Start of code ###########
##################################

dfsBoard = []
myString = ARGV[0]
for i in 0..483
	dfsBoard[i] = myString[i]
end

testBoard = Marshal.load(Marshal.dump(dfsBoard));

puts "-------------------------"
puts "DFS Search Maze Result"
puts "-------------------------"


puts "Running Depth First Search"
$nodesToVisit.push(23);
applyDfs(dfsBoard,testBoard);

puts "Solutions found: " + $solutionCounter.to_s;
puts "Solutions missing: " + (5 - $solutionCounter).to_s;








